/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */
package com.acworks.acroute.v2;

import com.acworks.acroute.v2.impl.PathAwareGraphImpl;
import com.acworks.acroute.v2.impl.PathImpl;
import java.util.ArrayList;
import java.util.Collections;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

/**
 *
 * @author nikita
 */
public class PathBuilder {

    final private ImmutableGraph graph;
    final private Set<Path> inadmissiblePaths;
    private int partialPathsEvaluatedCounter = 0;

    public PathBuilder(ImmutableGraph graph) {
        assert graph != null;
        this.graph = graph;
        this.inadmissiblePaths = new HashSet<Path>();
    }

    public ImmutableGraph getGraph() {
        return graph;
    }

    public List<Path> findValidPaths() {

        Path path = new PathImpl(getGraph());
        return findHamiltonianPaths(path);
    }

    /**
     * traverse given path until a bitter end
     * @param path starting path
     * @return list of valid Hamiltonian paths containing given 'path'
     */
    private List<Path> findHamiltonianPaths(final Path path) {
        assert path != null;
        List<Path> hamiltonianPaths = new ArrayList<Path>();

        //final PathAwareGraph pag = new PathAwareGraphImpl(getGraph(), path);
        PathAwareGraph pag = getPathAwareGraphIfPathAdmissible(path);
        if (pag == null) {
            return Collections.EMPTY_LIST;
        }

        int pathCount = 0;

        while (true) {
            while (path.advanceToNextUnvisitedSuccessor(pag)) {
                pag = getPathAwareGraphIfPathAdmissible(path);
                while (pag == null && !path.isAtStartNode()) {
                    path.popCurrentNode();
                    pag = getPathAwareGraphIfPathAdmissible(path);
                }
            }

            //reached end of this path

            pathCount++;
            if (pathCount % 10000 == 0) {
                System.out.println("pathCount=" + pathCount);
            }
            
            if (path.isHamiltonianPath()) {
                hamiltonianPaths.add(path);
            }
            inadmissiblePaths.add(path);

            if (path.isAtStartNode()) {
                break;
            } else {
                path.popCurrentNode();
                pag = getPathAwareGraphIfPathAdmissible(path);
            }
        }

        System.out.println("final pathCount=" + pathCount + ", pathsEvaluated=" + partialPathsEvaluatedCounter);

        return hamiltonianPaths;

        //OLD impl below
//
//
//        if (!inadmissiblePaths.contains(path) && pag.isPartialPathAdmissible()) {
//
//            //if possible, advance to the next unvisited successor
//            if (path.advanceToNextUnvisitedSuccessor(pag)) {
//                findHamiltonianPaths(path, hamiltonianPaths);
//            } else {
//
//                //end of path
//                if (path.isHamiltonianPath()) {
//                    hamiltonianPaths.add(path);
//                }
//                inadmissiblePaths.add(path);
//                if (!path.isAtStartNode()) {
//                    path.popCurrentNode(); //marks node as deleted
//                    findHamiltonianPaths(path, hamiltonianPaths);
//                }
//            }
//        } else if (!path.isAtStartNode()) {
//            path.popCurrentNode(); //marks node as deleted
//            findHamiltonianPaths(path, hamiltonianPaths);
//        }
//
//        //done
    }

    /**
     *
     * @param partialPath
     * @return PathAwareGraph or null if path isn't admissible
     */
    public PathAwareGraph getPathAwareGraphIfPathAdmissible(Path partialPath) {
        assert partialPath != null;

        PathAwareGraph pag = null;

        //defer pag init - relatively expensive
        if (!inadmissiblePaths.contains(partialPath)) {

            pag = new PathAwareGraphImpl(graph, partialPath);
            if (!pag.isPartialPathAdmissible()) {
                pag = null;
            }
            partialPathsEvaluatedCounter++;
            if (partialPathsEvaluatedCounter % 10000 == 0) {
                System.out.println("partialPathsEvaluatedCounter=" + partialPathsEvaluatedCounter);
            }
        }

        return pag;
    }

    public boolean isPathAdmissible(Path partialPath) {
        return getPathAwareGraphIfPathAdmissible(partialPath) != null;
    }
}
